package com.example.demo.leetcode.top100;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _65在排序数组中查找元素的第一个和最后一个位置
 * @description
 * @date 2023/06/23 10:29
 * <p>
 * ******************************************************
 */
public class _65在排序数组中查找元素的第一个和最后一个位置 {

    public int[] searchRange(int[] nums, int target) {
        return new int[]{left(nums, 0, nums.length - 1, target), right(nums, 0, nums.length - 1, target)};
    }

    private int right(int[] nums, int left, int right, int target) {
        while (left <= right) {
            int mid = right - (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                left = mid + 1;
            }
        }
        return left - 1 >= 0 && nums[left - 1] == target ? left - 1 : -1;
    }

    private int left(int[] nums, int left, int right, int target) {
        while (left <= right) {
            int mid = right - (right - left) / 2;

            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left < nums.length && nums[left - 1] == target ? left - 1 : -1;
    }
}
